package problems;

/**
 * Created with IntelliJ IDEA.
 * User: Vikas.Bhardwaj
 * Date: 5/23/12
 * Time: 1:43 PM
 * To change this template use File | Settings | File Templates.
 */
public class BinarySearchProblems {

    public static double findSqrt(int x){

        int numDigits = String.valueOf(x).length();
        int exp = numDigits%2==0 ? (numDigits-2)/2 : (numDigits-1)/2;
        double oldx = numDigits%2==0 ? 6*Math.pow(10,exp) : 2 * Math.pow(10,exp);
        double newx = 0.0;
        double diff = 100;
        int numIter = 0;
        while(diff>=0.0001){
            newx = 0.5*( oldx + x/oldx);
            diff = Math.abs(newx - oldx);
            numIter++;
            oldx = newx;
        }
        System.out.println("Sqrt of "+x+" is "+newx+" found in "+numIter+" iterations");
        return newx;
    }

    /**
     * Given a matrix of numbers, sorted by rows and columns, find if the given number is present
     * @param A : the matrix
     * @param x : the number to find
     * @return : true if the number is found.
     */
    public static boolean matrixSearch(int[][] A, int x){
        boolean found = false;
        int i = A.length-1;
        int jMax = A[0].length-1;
        int j = 0;

        while(!found && i >= 0 && j <= jMax){
            if(A[i][j] == x){
                found = true;
            }else if(A[i][j] > x){
                    j++;
            } else {
                i--;
            }
        }

        return found;
    }

}
